/*
	解法：给n求下一个数 + 判断是否进入一个循环
	为什么：不管n多大，最后一定会变成1 或 在 [1, 243] 范围内循环
	时间复杂度：O(log n)，空间复杂度：O(log n)
 */

#include <iostream>
#include <unordered_set>

using namespace std;

class Solution
{
public:
	bool isHappy(int n)
	{
		unordered_set<int> seen;
		
		while (n != 1 && !seen.count(n))
		{
			seen.insert(n);
			n = getNext(n);
		}
		
		if (n == 1)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	
private:
	int getNext(int n)
	{
		int sum = 0;
		while (n > 0)
		{
			int digit = n % 10;		// 取出当前数字 n 的最低位（个位）数字
			sum += digit * digit;	// 将该位数字的平方加到总和 sum 中
			n /= 10;				// 丢弃最低位，继续处理下一位数字
		}
		return sum;
	}
};

int main()
{
	Solution solution;
	
	int n1 = 1;
	int n2 = 2;
	
	cout << "n = " << n1 << " → " << boolalpha << solution.isHappy(n1) << endl;		//boolapha是<iostream>中一个用于控制 bool 类型输出格式的 I/O 操作符
	cout << "n = " << n2 << " → " << boolalpha << solution.isHappy(n2) << endl;		//把 true/false 显示成字符串
	
	return 0;
}


